package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author huangweiyue
 * @version v1.0
 * @task 206 https://leetcode-cn.com/problems/reverse-linked-list/
 * @description 反转链表
 * @date Created in 2021-07-04
 */
public class ReverseList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        System.out.println(head);
        System.out.println("reverse");
//        System.out.println(reverseList(head));
        System.out.println(reverseList2(head));

    }

    /**
     * 我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
     * 第二个指针 cur 指向 head，然后不断遍历 cur。
     * 每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
     * 都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            //当前节点的next指向pre节点
            curr.next = prev;
            //前一个节点的值赋值为当前节点
            prev = curr;
            //当前结点赋值为next，继续遍历
            curr = next;
        }
        return prev;
    }

    /**
     * 暴力解法 占用内存空间
     */
    public static ListNode reverseList2(ListNode head) {
        List<Integer> integerList=new ArrayList<>();
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            integerList.add(curr.val);
            curr = next;
        }
        Collections.reverse(integerList);
        ListNode root = new ListNode(integerList.get(0));
        ListNode other = root;
        for (int i = 1; i < integerList.size(); i++) {
            //先暂存起来
            ListNode temp = new ListNode(integerList.get(i));
            //给next赋值
            other.next = temp;
            //移动指针
            other = temp;
        }
        return root;
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
